#include <iostream>
#include <cassert>

using namespace std;
enum Color
{
    RED,
    BLACK,
};

template <class K>
struct RBTreeNode
{
    RBTreeNode<K> *_left;
    RBTreeNode<K> *_right;
    RBTreeNode<K> *_parent;
    K _key;
    Color _cor;

    RBTreeNode(const K &key)
        : _left(nullptr), _right(nullptr), _parent(nullptr),
          _key(key), _cor(RED)
    {
    }
};

template <class K>
class RBTree
{
    typedef RBTreeNode<K> Node;

public:
    bool Insert(const K &key)
    {
        if (_root == nullptr)
        {
            _root = new Node(key);
            _root->_cor = BLACK;
            return true;

            Node *parent = nullptr;
            Node *cur = _root;

            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else // cur->key == key
                {
                    return false;
                }
            }
            cur = new Node(key);
            cur->_cor = RED;
            cur->parent = parent;

            if (cur->_key < parent->_key)
            {
                parent->_left = cur;
            }
            else
            {
                parent->_right = cur;
            }

            // 默认新插入节点为红色，若违反红黑树规则，则需要调整
            while (parent && parent->_cor == RED)
            {
                // 调整动作
                Node *grandfather = parent->_parent;
                if (grandfather->_left == parent)
                {
                    Node *uncle = grandfather->_right;
                    if (uncle && uncle->_cor == RED)
                    {
                        // 情况1

                        parent->_cor = uncle->_cor = BLACK;
                        grandfather->_cor = RED;

                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    else // unle不存在或uncle存在且为黑
                    {
                        if (parent->_left == cur)
                        {
                            // 情况2
                            RotateR(grandfather);
                            parent->_cor = BLACK;
                            grandfather->_cor = RED;
                        }
                        else if (parent->_right == cur)
                        {
                            // 情况3
                            RotateL(parent);
                            RotateR(grandfather);
                            cur->_cor = BLACK;
                            grandfather->_cor = RED;
                        }

                        break; // 关键
                    }
                }
                else if (grandfather->_right == parent) // 镜像即可
                {
                    Node *uncle = grandfather->_left;
                    if (uncle && uncle->_cor == RED)
                    {
                        parent->_cor = uncle->_cor = BLACK;
                        grandfather->_cor = RED;

                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    else
                    {
                        if (parent->_right == cur)
                        {
                            // 情况2
                            RotateL(grandfather);
                            parent->_cor = BLACK;
                            grandfather->_cor = RED;
                        }
                        else if (parent->_left == cur)
                        {
                            // 情况3
                            RotateR(parent);
                            RotateL(grandfather);
                            cur->_cor = BLACK;
                            grandfather->_cor = RED;
                        }
                        break; // 关键
                    }
                }
            }

            _root->_cor = BLACK; // 确保根节点颜色为黑色
            return true;
        }
    }

    void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if(subRL)
			subRL->_parent = parent;

		Node* parentParent = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;
		
		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}

		
	}

	void  RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parentParent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}
	}

private:
    Node *_root = nullptr;
};

template <class K>
void PrintTree(const RBTreeNode<K>* node, int depth = 0, bool isLeft = true) {
    if (node != nullptr) {
        PrintTree(node->_right, depth + 1, false);
        for (int i = 0; i < depth; ++i) {
            std::cout << "  ";
        }
        if (isLeft) {
            std::cout << "(";
        } else {
            std::cout << ")";
        }
        std::cout << node->_key << ", Color: " << (node->_cor == RED ? "RED" : "BLACK") << std::endl;
    }
}

